UVa/10446 - The marriage interview/10446.cpp

   1 /*
   2   Problem: 10446 - The Marriage Interview :-)
   3
   4   Author: Andrés Mejía-Posada
   5
   6   Method: Top down dynamic programming with memoization.
   7
   8   Accepted.
   9  */
  10 #include <iostream>
  11
  12 using namespace std;
  13
  14 unsigned long long memo[62][62];
  15
  16 unsigned long long trib(int n, int back){
  17   if (n <= 1) return 1;
  18   if (memo[n][back] == -1){
  19     memo[n][back] = 1; //Esta invocación
  20     for(int i=1; i<=back; i++){
  21       memo[n][back] += trib(n-i, back);
  22     }
  23   }
  24   return memo[n][back];
  25 }
  26
  27 int main(){
  28   int n, back, C = 1;
  29   memset(memo, -1, sizeof memo);
  30   while (cin >> n >> back &&  n <= 60){
  31     cout << "Case " << C++ << ": " << trib(n, back) << endl;
  32   }
  33   return 0;
  34 }